In the study of graph coloring problems in mathematics and computer science, a greedy coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings do not in general use the minimum number of colors possible; however they have been used in mathematics as a technique for proving other results about colorings and in computer science as a heuristic to find colorings with few colors.
The perfectly orderable graphs, defined by the optimality of the greedy algorithm on their induced subgraphs, form an important subclass of perfect graphs.
Contents |
A crown graph (a complete bipartite graph Kn,n, with the edges of a perfect matching removed) is a particularly bad case for greedy coloring: if the vertex ordering places two vertices consecutively whenever they belong to one of the pairs of the removed matching, then a greedy coloring will use n colors, while the optimal number of colors for this graph is two. There also exist graphs such that with high probability a randomly chosen vertex ordering leads to a number of colors much larger than the minimum.[1] Therefore, it is of some importance in greedy coloring to choose the vertex ordering carefully.
The vertices of any graph may always be ordered in such a way that the greedy algorithm produces an optimal coloring. For, given any optimal coloring in which the smallest color set is maximal, the second color set is maximal with respect to the first color set, etc., one may order the vertices by their colors. Then when one uses a greedy algorithm with this order, the resulting coloring is automatically optimal. However, due to the NP-completeness of the graph coloring problem, it is difficult to find an ordering that leads to a minimum number of colors. For this reason, heuristics have been used that attempt to reduce the number of colors while not guaranteeing an optimal number of colors.
A commonly used ordering for greedy coloring is to choose a vertex v of minimum degree, order the remaining vertices, and then place v last in the ordering. If every subgraph of a graph G contains a vertex of degree at most d, then the greedy coloring for this ordering will use at most d + 1 colors.[2] The smallest such d is commonly known as the degeneracy of the graph.
For a graph of maximum degree Δ, any greedy coloring will use at most Δ + 1 colors. Brooks' theorem states that with two exceptions (cliques and odd cycles) at most Δ colors are needed, and one proof of Brooks' theorem involves finding a vertex ordering in which the first two vertices are adjacent to the final vertex but not adjacent to each other, so that a greedy coloring for this ordering uses only Δ colors.[3]
It is NP-complete to determine, for a given graph G and number k, whether some ordering of the vertices of G forces the greedy algorithm to use k or more colors. In particular, this means that it is difficult to find the worst ordering for G.[4]
It is possible to define a greedy coloring algorithm in which the vertices of the given graph are colored in a given sequence but in which the color chosen for each vertex is not necessarily the first available color; alternative color selection strategies have been studied within the framework of online algorithms. In the online graph-coloring problem, vertices of a graph are presented one at a time in an arbitrary order to a coloring algorithm; the algorithm must choose a color for each vertex, based only on the colors of and adjacencies among already-processed vertices. In this context, one measures the quality of a color selection strategy by its competitive ratio, the ratio between the number of colors it uses and the optimal number of colors for the given graph.
If no additional restrictions on the graph are given, the optimal competitive ratio is only slightly sublinear.[5] However, for interval graphs, a constant competitive ratio is possible,[6] while for bipartite graphs and sparse graphs a logarithmic ratio can be achieved.[7] Indeed, for sparse graphs, the standard greedy coloring strategy of choosing the first available color achieves this competitive ratio, and it is possible to prove a matching lower bound on the competitive ratio of any online coloring algorithm.[7]
A graph G is said to be perfectly orderable if there exists an ordering π of the vertices of G, such that any induced subgraph is optimally colored by the greedy algorithm using the subsequence of π induced by the vertices of the subgraph. That is, π must not only be an optimal ordering for the greedy algorithm for G, but for every induced subgraph of G. An ordering π has this property exactly when there do not exist four vertices a, b, c, and d for which abcd is an induced path, a appears before b in the ordering, and c appears after d in the ordering.[8] Perfectly orderable graphs form a subset of the perfect graphs,[8] but are NP-complete to recognize.[9]
Chordal graphs are perfectly orderable; a perfect ordering of a chordal graph may be found by reversing a perfect elimination ordering for the graph. Thus, applying greedy coloring to a perfect ordering provides an efficient algorithm for optimally coloring chordal graphs. Comparability graphs are also perfectly orderable, with a perfect ordering being given by a topological ordering of a transitive orientation of the graph.[8]
A concept intermediate between the perfect elimination ordering of a chordal graph and a perfect ordering is a semiperfect elimination ordering: in an elimination ordering, there is no three-vertex induced path in which the middle vertex is the first of the three to be eliminated, and in a semiperfect elimination ordering, there is no four-vertex induced path in which one of the two middle vertices is the first to be eliminated. The reverse of this ordering therefore satisfies the requirements of a perfect ordering, so graphs with semiperfect elimination orderings are perfectly orderable.[10] In particular, the same lexicographic breadth-first search algorithm used to find perfect elimination orders of chordal graphs can be used to find semiperfect elimination orders of distance-hereditary graphs, which are therefore also perfectly orderable.[11]
Several additional classes of perfectly orderable graphs are known.[12]